Math 512: Finite Model Theory k-variable logic 0-1 laws

John Baldwin

March 16, 1997

references: Vaananen, chapter 4, E and F chapter 2 and chapter 7, Hella, Kolaitis, and Luosto, Almost everywhere equivalence of logics in finite model theory, Bull of Sym. Logic, Dec. 1996. 422-444. Dawar, Lindell, and Weinstein, Infinitary logic and inductive definability over finite structures. (on Weinstein’s web site reachable from FMT website via people) Monica McArthur, Convergence and 0-1 laws for L_{∞,ω}^{ω} under arbitrary measures, Lecture Notes in Computer Science 933, Springer, Computer Science Logic, edited by Pacholski and Tiuryn.

We restrict our attention briefly to graphs. This restriction is only for ease of writing. Recall that ϕ_{k} denotes the k-extension sentence. Note that if H and H′ are finite graphs and both satisfy ϕ_{k} then they are k-pebble game equivalent, i.e. L^{k}-equivalent. This yields.

Theorem 0.1 (Kolaitis-Vardi 92). The 0-1 law holds for constant probabilities for the language L^{k}.

Proof. Suppose ψ ∈ L^{k} and there is a graph G such that G ⊧ ϕ_{k} ∧ ψ. Then every graph which satisfies ϕ_{k} is L^{k}-equivalent to G and hence satisfies ψ. If there is no such G, apply the argument to ¬ψ.

Of course this implies the 0-1 law for F P. Here is a somewhat weaker but much softer result.

0.2 Lemma. Ryll-Nardjewski’s theorem.

See Chang-Keisler, Sacks, etc. statement in my book.

The following result is improved several paragraphs down. I leave it here as a sample of how one to prove the almost everywhere elimination of a generalized quantifier by syntactic approximation. The more general result for L_{∞,ω}^{k} is done by noticing that the appropriate E-F game can be described in the smaller logic.

0.3 Theorem. Suppose K is a class of finite structures, P_{n} is a probability measure on the models of K with cardinality n, the 0-1 law for FO holds for P and the almost sure theory T is ℵ_{0}-categorical. Then the 0-1 law for LFP holds for P on K. In fact, for every sentence θ of LFP there is a sentence θ′ in FO such that a.e. θ ↔ θ′.

Proof. By induction on quantifier complexity, we need only find a formula θ′(\overline{x}) equivalent to θ when θ(\overline{x}) has the form [LF P_{\overline{y},X}ϕ(\overline{y}, X)]\overline{x} and ϕ(\overline{x}, X) is positive in X. We have seen θ(\overline{x}) ≡ ⋁_{i,ω} ϕ_{i}(\overline{x}) where each ϕ_{i} is first order. Let M be the countable model of T. By ℵ_{0}-categoricity, there are only finitely many lg(\overline{x}) formulas. So for some m we must have M ⊧ (∀\overline{x})ϕ_{i}(\overline{x}) ≡ ϕ_{i+m}(\overline{x}). Since the ϕ_{i} are increasing this implies M ⊧ (∀\overline{x})ϕ_{i}(\overline{x}) ≡ ϕ_{i+1}(\overline{x}). Call this sentence χ. For some sentence ρ ∈ T, we have ρ → χ. On any finite model of ρ, [LF P_{\overline{y},X}ϕ(\overline{y}, X)](\overline{x}) ≡ ϕ_{i}(\overline{x}) Since ρ has limit probability 1, we finish.

We turn to the Kolaitis et al notion of almost everywhere equivalence of logics. P denotes a sequence of measures P_{n} on the set of τ stuctures with universe n (which I will denote τ_{n}). For any class K of finite τ structures P (K) = lim P_{n}(K ∩ τ_{n}) if it exists.

0.4 Definition. The logics L and L′ are almost everywhere equivalent with respect to the probability measure P if there exists a collection C of finite models such that P (C) = 1 and for every sentence θ of L there is a sentence θ′ of L′ such that θ and θ′ are equivalent on C (and conversely).

0.5 Theorem. F O and L_{∞,ω}^{ω} are almost everywhere equivalent with respect to the uniform distribution.

Fix lg(\overline{a}) = k ≤ s, k′ = min(k + 1, s). Let \overline{a}^{i} denote the result of omitting the ith term from \overline{a} if i < k and \overline{a}^{i} = \overline{a} if i ≥ k.

0.6 Definition. We define the s-Scott sentence of an ℵ_{0}-categorical (possibly finite) structure M. Let σ range through the types of M with length at most s. We let σ^{i} be the type of \overline{a}^{i} for some (any) \overline{a} ∈ M which realizes σ.

S^{k}(M) denotes the set of all (first order) k-types in M. Let S = ⋃_{j≤s} S^{j}(M); so σ ∈ S.

ψ_{σ}^{0} = ⋀ quantifier free formulas in σ

ψ_{σ}^{m+1}(\overline{v}) = ψ_{σ}^{0}(\overline{v}) ∧ ⋀_{i<k′} ⋀_{σ^{i}⊆τ∈S^{k′}(M)}(∃v_{i})ψ_{τ}^{m}(\overline{v}^{i}v_{i}) ∧ (∀v_{i}) ⋁_{σ^{i}⊆τ∈S^{k′}(M)} ψ_{τ}^{m}(\overline{v}^{i}v_{i}).

Let X_{σ}^{m} = \{\overline{a} ∈ M : M ⊧ ψ_{σ}^{m}(\overline{a})\}. Then X_{σ}^{m} ⊇ X_{σ}^{m+1} and some X_{σ}^{m} = X_{σ}^{m+1} by ℵ_{0} categoricity; call this number m_{σ}. Let m_{M} be the max of the m_{σ} for σ ∈ S. The s-Scott sentence ϕ_{M} of M, ϕ_{M}^{s} is

ψ_{<>}^{m_{M}} ∧ ⋀_{σ∈S}(∀x_{1} … ∀x_{s})[ψ_{σ}^{m_{M}} → ψ_{σ}^{m_{M} +1}].

Note that although we constructed ϕ_{M}^{s} by indexing on first order types in arbitrarily many variables, the sentence is in F O^{s}. There are a finite number of ≤ s types σ realized in M and each is principal with first order generator, θ_{σ}. Let χ_{M}^{s} assert that these formulas partition M^{<s}:

⋀_{i<s}(∀v_{0}, … v_{i})( ⋁_{lg(σ)=i} θ_{σ}(v_{0}, … v_{i}) ∧ ⋀_{{lg(σ)=lg(τ)=i \atop σ≠τ}}(θ_{σ} → ¬θ_{τ})) ∧ ⋀_{lg(σ)=i}(∃v_{0}, … v_{i})θ_{σ}(v_{0}, … v_{i}).

I continue to use the notion of s-back and forth I defined in class. But notice that Definition 4 of Dawar, Lindell, Weinstein is much slicker.

0.7 Lemma. If A, B both satisfy an s-Scott sentence ϕ_{M}^{s} and the sentence χ_{M}^{s} then A ≡_{L_{∞,ω}^{s}} B.

Proof. Define an s-back and forth between A and B consisting of those ⟨\overline{a}, \overline{b}⟩ such that B ⊧ ϕ_{σ}^{s}(\overline{a}) where σ = \{ρ(\overline{v}) : A ⊧ ρ(\overline{a})\}. Since both A and B satisfy χ_{M}^{s}, each < s tuple from A or B satisfies exactly one formula θ_{σ} .

This result may not be explicitly formulated in print but it was know to Kolaitis et al.

0.8 Theorem. Suppose K is a class of finite structures, P_{n} is a probability measure on the models of K with cardinality n, the 0-1 law for FO holds for P and the almost sure theory T is ℵ_{0}-categorical. Then the 0-1 law for L^{ω} holds for P on K. In fact, F O and L_{∞,ω}^{ω} are almost everywhere equivalent with respect to P.

Proof. Fix M the countable model of the almost sure theory. So α_{M}^{s} = ϕ_{M}^{s} ∧ χ_{M}^{s} has probability 1. Moreover, if the finite models A, B both satisfy α_{M}^{s}, they are L_{∞,ω}^{s}- equivalent. The proof now follows Hella, Kolaitis, and Luosto. Let C_{s} be the finite models of the extension axiom α_{M}^{s}. Define a sequence j_{i} such that if n ≥ j_{k}, P_{n}(α_{M}^{s}) ≥ 1 − 2^{s}. Let C′_{s} be the members of C_{s} with cardinality greater than j_{s}. (Clearly C_{s} − C′_{s} is finite.) Let C = ⋃_{i<ω}(C′_{i} − C′_{i+1}. Then P (C) = 1. Now let ϕ ∈ L_{∞,ω}^{ω}. In particular, for some m, ϕ ∈ L_{∞,ω}^{m}. If α_{M}^{m} and ϕ are consistent, ϕ holds on all of C′_{m} (otherwise ¬ϕ does) and (noting that m < n implies C_{m} ⊆ C_{n}) there are only finitely many members of C − C_{m}. Let ϕ′ be α_{M}^{m} ∨ ρ where ρ describes the members of C − C_{m} that satisfy ϕ.

Now fix a probability measure on a class of finite models and assume the first order theory has a 0-1-law with almost sure theory T_{ran}. The next few paragraphs combine ideas of McArthur and D,L,W.

An F O^{k}-type p is a maximal set of F O^{k} formulas consistent with T_{ran}, p is k-principal if it is generated by a formula in F O^{k}.

0.9 Lemma. Every F O^{k}-type p of T_{ran} which is realized in a finite model is k-principal.

Proof. Let ⟨A, \overline{a}⟩ realize p. The k-Scott sentence of ⟨A, \overline{a}⟩ is the generating formula.

McArthur proved a somewhat more general version of the sufficiency condition for almost everywhere equivalence of F O and L_{∞,ω}^{ω}.

0.10 Theorem. Let T_{ran} be the almost sure first order theory of class K with respect to a probability P. If for each k there are only finitely many F O^{s}-types over T in at most s elements, then F O and L_{∞,ω}^{ω} are almost everywhere equivalent on K.

Proof. The proof is as before. Just note that it is sufficient for χ_{M}^{s} to code a partition (and it can be determined by a theory not a particular model).

McArthur proves the following converse.

0.11 Theorem. If T_{ran} is the almost sure theory of K, and there is an L_{∞,ω}^{s}-0-1-law for K, then every F O^{s} type of T_{r}an is realized in a finite model.

Proof. Let p be an F O^{s} type of T_{r}an is not realized in any finite model. Then for each n there is a formula ϕ_{n}(\overline{x}) ∈ p which can not be realized in a model with fewer than n elements. WOLOG, ϕ_{n+1} → ϕ_{n}. Choose m_{n} such that for m ≥ m_{n}, P_{m}((∃\overline{x})ϕ_{n}(\overline{x}) > 1 − 1/n. Define f(n) by recursion, letting f(0) being some arbitrary n_{o} and f(n + 1) = m_{f(n)} + 1. Consider the L_{∞,ω}^{s} sentence:

θ = ⋀((∃\overline{x})[ϕ_{f(2n)}(\overline{x}) → ϕ_{f(2n+1)}(\overline{x})].

Now, lim_{i→∞} P_{m_{f(2i)}}θ = 0

and lim_{i→∞} P_{m_{f(2i+1)}}θ = 1.

Thus there is no 0-1 law.